class RandomListNode:
    def __init__(self, x):
        self.label = x
        self.next = None
        self.random = None

class Solution:
    # 返回 RandomListNode
    def Clone(self, pHead):
        temp_node = pHead
        while temp_node is not None:
            new_node = RandomListNode(temp_node.label)
            new_node.next = temp_node.next
            temp_node.next = new_node
            temp_node = new_node.next
        temp_node = pHead
        while temp_node is not None:
            next_node = temp_node.next
            if temp_node.random is not None:
                next_node.random = temp_node.random.next
            temp_node = next_node.next
        temp_node = pHead
        while temp_node.next is not None:
            new_temp_node = temp_node.next
            temp_node.next = new_temp_node.next
            temp_node = new_temp_node
        return pHead.next